package Sort;

import java.util.Arrays;

public class Qsort {
//    public int[] getLeastNumbers(int[] nums, int k)
//    {
//        qsort(nums, 0, nums.length - 1, k);
//        int[] ret = new int[k];
//        for(int i = 0; i < k; i++)
//            ret[i] = nums[i];
//        return ret;
//    }
//    public void qsort(int[] nums, int l, int r, int k)
//    {
//        if(l >= r) return;
//        // 1. 随机选择⼀个基准元素 + 数组分三块
//        int key = nums[new Random().nextInt(r - l + 1) + l];
//        int left = l - 1, right = r + 1, i = l;
//        while(i < right)
//        {
//            if(nums[i] < key) swap(nums, ++left, i++);
//            else if(nums[i] == key) i++;
//            else swap(nums, --right, i);
//        }
//        // 2. 分类讨论
//        int a = left - l + 1, b = right - left - 1;
//        if(a > k) qsort(nums, l, left, k);
//        else if(a + b >= k) return;
//        else qsort(nums, right, r, k - a - b);
//    }
//    public void swap(int[] nums, int i, int j)
//    {
//        int t = nums[i];
//        nums[i] = nums[j];
//        nums[j] = t;
//    }
//    public int findKthLargest(int[] nums, int k)
//    {
//        return qsort(nums, 0, nums.length - 1, k);
//    }
//    public int qsort(int[] nums, int l, int r, int k)
//    {
//        if(l == r)
//        {
//            return nums[l];
//        }
//        // 1. 按照随机选择的基准元素，将数组分三块
//        int key = nums[new Random().nextInt(r - l + 1) + l];
//        int left = l - 1, right = r + 1, i = l;
//        while(i < right)
//        {
//            if(nums[i] < key) swap(nums, ++left, i++);
//            else if(nums[i] == key) i++;
//            else swap(nums, --right, i);
//        }
//        // 2. 分情况讨论
//        int c = r - right + 1, b = right - left - 1;
//        if(c >= k) return qsort(nums, right, r, k);
//        else if(c + b >= k) return key;
//        else return qsort(nums, l, left, k - b - c);
//    }
//    public void swap(int[] nums, int i, int j)
//    {
//        int t = nums[i];
//        nums[i] = nums[j];
//        nums[j] = t;
//    }
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6,0};
        qort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void qort(int[] arr,int l,int r){
        if(l >= r) return;
        int mid = arr[l+r>>1];
        int i = l-1;
        int j = r+1;
        while (i < j){
            do i++; while (arr[i] < mid);
            do j--; while (arr[j] > mid);
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        qort(arr,l,j);
        qort(arr,j+1,r);
    }
}
